package Test_1117;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */


public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }
    public int i=0;
    //前序遍历:根左右
    public void preOrder(TreeNode root){
        if(root==null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历：左根右
    public  void inOrder(TreeNode root){
        if(root==null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //后续遍历：左右根
    public void postOrder(TreeNode root){
        if(root==null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //遍历思路：
    List<Character> list=new ArrayList<>();
    public List<Character> preorderTraversal(TreeNode root) {
          if(root==null)
              return list;
          list.add(root.val);
          preorderTraversal(root.left);
          preorderTraversal(root.right);
          return list;
    }
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null)
            return list;
        list.add(root.val);
        List<Character> leftTree=preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Character> rightTree=preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //获取长度
    //遍历：
    public static int nodeSize=0;
    public void  size(TreeNode root){
        if(root==null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }
    public int  size1(TreeNode root){
        if(root==null){
            return 0;
        }
        nodeSize++;
        int val1=size1(root.left);
        int val2=size1(root.right);
        return val1+val2+1;
    }
    public static int leafnodeSize=0;
    //叶子节点个数
    public void  getLeafNodeCount(TreeNode root){
        if(root==null){
            return ;
        }
        if(root.left==null &&root.right==null ){
            leafnodeSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    public int  getLeafNodeCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        return getLeafNodeCount1(root.left)+
                getLeafNodeCount1(root.right);
    }
    //获取第k层节点个数
    public int  getKLeafNodeCount(TreeNode root,int k){
        if(root==null){
            return -1;
        }
        if(k==1){
            return 1;
        }
        return getKLeafNodeCount(root.left,k-1)+getKLeafNodeCount(root.right,k-1);
    }
   /* public int getHeight(TreeNode root){

    }*/
}
